class Solution(object):
    def searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        nRow = len(matrix)
        nCol = len(matrix[0])
        def search(rbegin, rend, cbegin, cend):
            if rbegin>rend or cbegin>cend:
                return False
            if rbegin==rend:
                while cbegin<=cend:
                    mid = (cbegin+cend)//2
                    if target<matrix[rbegin][mid]:
                        cend=mid-1
                    elif target>matrix[rbegin][mid]:
                        cbegin=mid+1
                    else:
                        return True
                return False
            if cbegin==cend:
                while rbegin<=rend:
                    mid = (rbegin+rend)//2
                    if target<matrix[mid][cbegin]:
                        rend=mid-1
                    elif target>matrix[mid][cbegin]:
                        rbegin=mid+1
                    else:
                        return True
                return False
            r, c = (rbegin+rend)//2, (cbegin+cend)//2
            val = matrix[r][c]
            if target<val:
                if search(rbegin, r-1, cbegin, c-1): return True
                if search(r, rend, cbegin, c-1): return True
                if search(rbegin, r-1, c, cend): return True
                return False
            elif target>val:
                if search(rbegin, r, c+1, cend): return True
                if search(r+1, rend, cbegin, c): return True
                if search(r+1, rend, c+1, cend): return True
                return False
            else:
                return True
        return search(0, nRow-1, 0, nCol-1)

matrix = [[1,2,3,4,5],[6,7,8,9,10],[11,12,13,14,15],[16,17,18,19,20],[21,22,23,24,25]]

print(Solution().searchMatrix(matrix, 12))